/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package opk.Solver;

import java.awt.Point;
import java.util.ArrayList;
import java.util.Collections;
import opk.Generator.Shape;

/**
 *
 * @author Dawid
 */
public class GrahamAlgorithm
{

    public GrahamAlgorithm()
    {
        this.resultPoints = new ArrayList<Point>();
        this.allPoints = new ArrayList<SortedPoint>();
    }

    private ArrayList<Point> resultPoints;
    private ArrayList<SortedPoint> allPoints;


    public  Shape getShapeAfterGraham(ArrayList<Shape> shapes)
    {
        Point pointWithMinY = getMinYPoint(shapes);

        for (Shape shape : shapes)
        {
            for (Point point : shape.nodes)
            {
                allPoints.add(new SortedPoint(point, pointWithMinY));
            }
        }
        allPoints.remove(pointWithMinY);
        allPoints.add(0, new SortedPoint(pointWithMinY, null));

        Collections.sort(allPoints, new PointsSortComparator(pointWithMinY));

        for (int i = 0; i < allPoints.size() - 1; ++i)
        {
           // while (allPoints.get(i).getAlfaValue() == allPoints.get(i + 1).getAlfaValue())
                while (allPoints.get(i).equals(allPoints.get(i + 1)))
            {
                allPoints.remove(i + 1);
                --i;
            }
        }

        push(allPoints.get(0));
        push(allPoints.get(1));
        push(allPoints.get(2));

        for (int i = 3; i < allPoints.size(); ++i)
        {
            while(isOnRight(nextToTop(), top(), allPoints.get(i)))
            {
                pop();
            }

            push(allPoints.get(i));
        }

        return new Shape(resultPoints);
    }

    public ResultShape getResultShapeAfterGraham(ArrayList<Shape> shapes)
    {
         Point pointWithMinY = getMinYPoint(shapes);

        for (Shape shape : shapes)
        {
            for (Point point : shape.nodes)
            {
                allPoints.add(new SortedPoint(point, pointWithMinY));
            }
        }
        allPoints.remove(pointWithMinY);
        allPoints.add(0, new SortedPoint(pointWithMinY, null));

        Collections.sort(allPoints, new PointsSortComparator(pointWithMinY));

        for (int i = 0; i < allPoints.size() - 1; ++i)
        {
           // while (allPoints.get(i).getAlfaValue() == allPoints.get(i + 1).getAlfaValue())
                while (allPoints.get(i).equals(allPoints.get(i + 1)))
            {
                allPoints.remove(i + 1);
                --i;
            }
        }
        
        push(allPoints.get(0));
        push(allPoints.get(1));
        push(allPoints.get(2));

        for (int i = 3; i < allPoints.size(); ++i)
        {
            while(isOnRight(nextToTop(), top(), allPoints.get(i)))
            {
                pop();
            }

            push(allPoints.get(i));
        }

        return new ResultShape(resultPoints);
    }

    private Point getMinYPoint(ArrayList<Shape> shapes)
    {
        Point pointWithMinY = shapes.get(0).nodes.get(0);
        
        for (Shape shape : shapes)
        {
            for (Point point : shape.nodes)
            {
                if (point.y < pointWithMinY.y)
                {
                    pointWithMinY = point;
                }
                else if (point.y == pointWithMinY.y)
                {
                    if (point.x < pointWithMinY.x)
                    {
                        pointWithMinY = point;
                    }
                }
            }
        }
        
        return pointWithMinY;
    }


    private  Point top()
    {
        return resultPoints.get(resultPoints.size() - 1);
    }

    private  Point nextToTop()
    {
        if (resultPoints.size() - 2 == -1)
        {
            System.out.println("aa");
        }
        return resultPoints.get(resultPoints.size() - 2);

    }

    private Point pop()
    {
        return resultPoints.remove(resultPoints.size() - 1);
    }

    private void push(Point point)
    {
        resultPoints.add(point);
    }

    private boolean isOnRight(Point vectorPoint1, Point vectorPoint2, Point point)
    {
        if (vectorPoint1.x * vectorPoint2.y + vectorPoint2.x * point.y + point.x * vectorPoint1.y
                - point.x * vectorPoint2.y - vectorPoint1.x * point.y - vectorPoint2.x * vectorPoint1.y <= 0)
        {
            return true;
        }
        else
        {
            return false;
        }
    }

    public void test()
    {

    //   new SortedPoint(new Point(565, 120), )

    }
}
